11. Pattern Matching [exercise]

Pattern Matching

Now that you know how to iterate through a 2D array, your next task will be to use what you've learned to help locate a robot in a 2D world based on some sensor measurements.

In this example, a robot is navigating a 4x5 orange and blue world, shown below. This robot also has a sensor that tells it the color of the square it's on top of and the color of the square directly to its right.

2D orange and blue world grid

2D orange and blue world grid

Robot sensing two color squares (one it's on top of, and one to its right)

Robot sensing two color squares (one it's on top of, and one to its right)

In Python code, the world and the sensor measurement can be represented by the following code (where 'o' stands for orange and 'b' for blue):

import numpy as np

world = np.array ([ ['o', 'b', 'o', 'o', 'b'],
                    ['o', 'o', 'b', 'o', 'o'],
                    ['b', 'o', 'o', 'b', 'o'],
                    ['b', 'o', 'o', 'o', 'o'] ])

measurement = ['b', 'o']

It's now easy for us to see that there are only a few places in the world that this robot can be, based on where the measurement lines up with color patterns on the world grid! In this exercise, it'll be up to you to find these locations programmatically.

Hint: You'll be adding values to a list. To add indices, please use the append function and the format list_name.append([row,column]). Further instructions can be found in the TODOs below.

Start Quiz:

import numpy as np

# A 4x5 robot world of characters 'o' and 'b'
world = np.array([ ['o', 'b', 'o', 'o', 'b'],
                   ['o', 'o', 'b', 'o', 'o'],
                   ['b', 'o', 'o', 'b', 'o'],
                   ['b', 'o', 'o', 'o', 'o'] ])

# Sensor measurement
measurement = ['b', 'o']

# This function takes in the world and the sensor measurement.
# Complete this function so that it returns the indices of the 
# likely robot locations, based on matching the measurement 
# with the color patterns in the world

def find_match(world, measurement):
    # Empty possible_locations list
    possible_locations = []
    
    ## TODO: Iterate through the world 
    ## Look at two adjacent indices at a time - the square the robot is 
    ## on top of and the square to its right
    ## (Making sure not to go past the bounds of the world)
    
    ## TODO: If two adjacent colors in the world match 
    ## the two colors in the sensor measurement
    ## Add those indices to the possible_locations list
    ## Append them in the format [row_index, column_index], i.e. [0, 0]
    
    return possible_locations
   

# This line runs the function and stores the output - do not delete 
locations = find_match(world, measurement)

import numpy as np

# A 4x5 robot world of characters 'o' and 'b'
world = np.array([ ['o', 'b', 'o', 'o', 'b'],
                   ['o', 'o', 'b', 'o', 'o'],
                   ['b', 'o', 'o', 'b', 'o'],
                   ['b', 'o', 'o', 'o', 'o'] ])

# Sensor measurement
measurement = ['b', 'o']

# This function takes in the world and the sensor measurement.
# Complete this function so that it returns the indices of the 
# likely robot locations, based on matching the measurement 
# with the color patterns in the world

def find_match(world, measurement):
    
    # Empty possible_locations list
    possible_locations = []
    
    # Store the number of columns and rows in the 2D array
    col = world.shape[1]
    row = world.shape[0]
    
    # Iterate through the entire array
    for i in range(0, row):
        for j in range (0, col):
            # Check that we are within the bounds of the world,
            # since we have to check two values, this means we're at
            # a row index < the number of columns (5) - 1
            # In other words j < 4
            if j < col - 1:
                # Check if a match is found by comparing array contents
                # and checking for equality at world[i][j] and 
                # one row to the right at world[i][j+1]
                
                # Values under and in front of the robot 
                under = world[i][j]
                in_front = world[i][j+1]
                
                if((measurement[0] == under) and (measurement[1] == in_front)):
                    # A match is found!
                    # Append the index that the robot is on
                    possible_locations.append([i,j])
    
    # Return the completed list
    return possible_locations
   

# This line runs the function and stores the output - do not delete 
locations = find_match(world, measurement)

import numpy as np

# A 4x5 robot world of characters 'o' and 'b'
world = np.array([ ['o', 'b', 'o', 'o', 'b'],
                   ['o', 'o', 'b', 'o', 'o'],
                   ['b', 'o', 'o', 'b', 'o'],
                   ['b', 'o', 'o', 'o', 'o'] ])

# Sensor measurement
measurement = ['b', 'o']

def find_match(world, measurement):
    
    # Empty possible_locations list
    possible_locations = []
    for y in range(world.shape[0]):
        for x in range(world.shape[1]):
            # if we are at the edge then we can't
            # look ahead. Use the "continue" statement
            # to proceed to the next step in the loop.
            if x == (world.shape[1]-1):
                continue
            
            m_under = world[y,x]   # get measurement UNDER robot
            m_front = world[y,x+1] # measurement in front of robot
            if [m_under, m_front] == measurement:
                possible_locations.append([y,x])
    
    return possible_locations
   

# This line runs the function and stores the output - do not delete 
locations = find_match(world, measurement)

User's Answer:

(Note: The answer done by the user is not guaranteed to be correct)

import numpy as np

# A 4x5 robot world of characters 'o' and 'b'
world = np.array([ ['o', 'b', 'o', 'o', 'b'],
                   ['o', 'o', 'b', 'o', 'o'],
                   ['b', 'o', 'o', 'b', 'o'],
                   ['b', 'o', 'o', 'o', 'o'] ])

# Sensor measurement
measurement = ['b', 'o']

# This function takes in the world and the sensor measurement.
# Complete this function so that it returns the indices of the 
# likely robot locations, based on matching the measurement 
# with the color patterns in the world

def find_match(world, measurement):
    # Empty possible_locations list
    possible_locations = []
    
    ## TODO: Iterate through the world 
    ## Look at two adjacent indices at a time - the square the robot is 
    ## on top of and the square to its right
    ## (Making sure not to go past the bounds of the world)
    
    ## TODO: If two adjacent colors in the world match 
    ## the two colors in the sensor measurement
    ## Add those indices to the possible_locations list
    ## Append them in the format [row_index, column_index], i.e. [0, 0]
    # Store the number of columns and rows in the 2D array
    col = world.shape[1]
    row = world.shape[0]
    
    # Iterate through the entire array
    for i in range(0, row):
        for j in range (0, col):
            # Check that we are within the bounds of the world,
            # since we have to check two values, this means we're at
            # a row index < the number of columns (5) - 1
            # In other words j < 4
            if j < col - 1:
                # Check if a match is found by comparing array contents
                # and checking for equality at world[i][j] and 
                # one row to the right at world[i][j+1]
                
                # Values under and in front of the robot 
                under = world[i][j]
                in_front = world[i][j+1]
                
                if((measurement[0] == under) and (measurement[1] == in_front)):
                    # A match is found!
                    # Append the index that the robot is on
                    possible_locations.append([i,j])
    
    return possible_locations
   

# This line runs the function and stores the output - do not delete 
locations = find_match(world, measurement)

import numpy as np

# A 4x5 robot world of characters 'o' and 'b'
world = np.array([ ['o', 'b', 'o', 'o', 'b'],
                   ['o', 'o', 'b', 'o', 'o'],
                   ['b', 'o', 'o', 'b', 'o'],
                   ['b', 'o', 'o', 'o', 'o'] ])

# Sensor measurement
measurement = ['b', 'o']

# This function takes in the world and the sensor measurement.
# Complete this function so that it returns the indices of the 
# likely robot locations, based on matching the measurement 
# with the color patterns in the world

def find_match(world, measurement):
    
    # Empty possible_locations list
    possible_locations = []
    
    # Store the number of columns and rows in the 2D array
    col = world.shape[1]
    row = world.shape[0]
    
    # Iterate through the entire array
    for i in range(0, row):
        for j in range (0, col):
            # Check that we are within the bounds of the world,
            # since we have to check two values, this means we're at
            # a row index < the number of columns (5) - 1
            # In other words j < 4
            if j < col - 1:
                # Check if a match is found by comparing array contents
                # and checking for equality at world[i][j] and 
                # one row to the right at world[i][j+1]
                
                # Values under and in front of the robot 
                under = world[i][j]
                in_front = world[i][j+1]
                
                if((measurement[0] == under) and (measurement[1] == in_front)):
                    # A match is found!
                    # Append the index that the robot is on
                    possible_locations.append([i,j])
    
    # Return the completed list
    return possible_locations
   

# This line runs the function and stores the output - do not delete 
locations = find_match(world, measurement)

import numpy as np

# A 4x5 robot world of characters 'o' and 'b'
world = np.array([ ['o', 'b', 'o', 'o', 'b'],
                   ['o', 'o', 'b', 'o', 'o'],
                   ['b', 'o', 'o', 'b', 'o'],
                   ['b', 'o', 'o', 'o', 'o'] ])

# Sensor measurement
measurement = ['b', 'o']

def find_match(world, measurement):
    
    # Empty possible_locations list
    possible_locations = []
    for y in range(world.shape[0]):
        for x in range(world.shape[1]):
            # if we are at the edge then we can't
            # look ahead. Use the "continue" statement
            # to proceed to the next step in the loop.
            if x == (world.shape[1]-1):
                continue
            
            m_under = world[y,x]   # get measurement UNDER robot
            m_front = world[y,x+1] # measurement in front of robot
            if [m_under, m_front] == measurement:
                possible_locations.append([y,x])
    
    return possible_locations
   

# This line runs the function and stores the output - do not delete 
locations = find_match(world, measurement)

Next Concept